/**
 * struct Interval {
 *	int start;
 *	int end;
 * };
 * 树的直径模板题
 * 提交地址： https://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3
 */

class Solution {
public:
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
    static const int N = 20010; 
    static const int INF = 0x3f3f3f3f; // 定义初始距离为无穷大
    
    struct Edge {
        int to, next, dis; // 存储图
    } e[N << 1];
    
    int head[N], idx = 1;
    
    void add(int a, int b, int c) {
        e[idx].to = b;
        e[idx].next = head[a];
        e[idx].dis = c;

        head[a] = idx++;
    }
    
    int far = -1; // 最远距离在的点
    int res = -1; // 最远距离
    
    void dfs(int u, int f = -1, int d = 0) {
        if (d > res) res = d, far = u;
        
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].dis;
            if (v != f) 
                dfs(v, u, d+w);
        }
    }
    
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        memset(head, -1, sizeof(head));
        
        for (int i = 0; i < n-1; i++) {
            add(Tree_edge[i].start, Tree_edge[i].end, Edge_value[i]);
            add(Tree_edge[i].end, Tree_edge[i].start, Edge_value[i]);
        }
        
        dfs(1);
        dfs(far);
        
        return res;
    }
};